package com.javaDemo.ti;

import com.javaDemo.node.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树层序遍历（之字形打印）
 * 
 * @author csy
 * @date 2020/6/5 01:18
 * @description 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，
 *              每一层的打印方向交替变化（第一层从左到右，第二层从右到左，第三层从左到右，以此类推）
 * 
 *              解题思路：
 *              1. 使用队列实现层序遍历
 *              2. 使用双端队列保存每层的结果
 *              3. 根据层数的奇偶性决定插入方向：
 *              - 偶数层：从左到右打印，添加到队列尾部
 *              - 奇数层：从右到左打印，添加到队列头部
 * 
 *              时间复杂度：O(n)，其中n为节点数量
 *              空间复杂度：O(n)，队列中最多存储n个节点
 * 
 *              参考：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
 */
public class BinaryTreeLevelOrderTraversal {

    /**
     * 按层序遍历打印二叉树（之字形）
     *
     * @param root 二叉树根节点
     * @return 层序遍历结果，每层的节点值存储在一个List中
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        // 存储最终结果
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        // 使用队列进行层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            // 使用双端队列存储当前层的节点值
            LinkedList<Integer> levelList = new LinkedList<>();
            int levelSize = queue.size();

            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

                // 根据层数决定插入方向
                if (result.size() % 2 == 0) {
                    // 偶数层 -> 从左到右
                    levelList.addLast(node.val);
                } else {
                    // 奇数层 -> 从右到左
                    levelList.addFirst(node.val);
                }

                // 将下一层的节点加入队列
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            result.add(levelList);
        }

        return result;
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 创建测试用例：[3,9,20,null,12,15,7]
        Integer[] values = { 3, 9, 20, null, 12, 15, 7 };
        TreeNode root = TreeNode.makeTree(values);

        // 执行层序遍历
        List<List<Integer>> result = levelOrder(root);

        // 打印结果
        System.out.println("二叉树的之字形层序遍历结果：");
        for (int i = 0; i < result.size(); i++) {
            System.out.printf("第%d层: %s%n", i + 1, result.get(i));
        }
    }
}